package org.example.stackandqueue;

import jdk.nashorn.internal.runtime.arrays.IntElements;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class largestRectangleArea {

    public static void main(String[] args) {
        int[] nums={2,1,5,6,2,3};
//        int result = solution1(nums);
//        int result = solution2(nums);
//        int result = solution(nums);
        int result = solution3(nums);
        System.out.println(result);
    }

    public static int solution(int[] heights){
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                 minHeight = Math.min(minHeight,heights[j]);
                 maxarea = Math.max(maxarea,minHeight * (j-i+1));
            }
        }
        return maxarea;
    }

    /**
     * [2,1,5,6,2,3]
     * 暴力破解法则
     * @return
     */
    public static int solution1(int[] heights){
        int len = heights.length;
        int area=0;
        for (int i = 0; i < len; i++) {
            int curHeight = heights[i];
            int left = i;

            while (left>0 && heights[left-1]>=curHeight){
                left--;
            }

            int right = i;
            while (right<len-1 && heights[right+1]>=curHeight){
                right++;
            }
            int width = right-left+1;
            int curArea = width * curHeight;
            area = Math.max(area,curArea);
        }
        return area;
    }

    /**
     * [2,1,5,6,2,3]
     * 嵌套循环三次才能完成，
     * 从左边开始循环遍历，i表示最左边的指针，j表示指针逐渐往后移动，k表示 i和j 两个柱子间最大的面积
     * @param heights
     * @return
     */
    public static int solution2(int[] heights){
        int maxarea = 0;

        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length ; j++) {
                int minHeight=Integer.MAX_VALUE;
                for (int k = i; k <=j ; k++) {
                    minHeight = Math.min(minHeight,heights[k]);
                }
                int width = j - i+1;
                maxarea = Math.max(maxarea,width * minHeight);
            }
        }
        return maxarea;
    }

    /**
     * 使用堆栈算法 [2,1,5,6,2,3]
     * @param heights
     * @return
     */
    public static int solution3(int[] heights){
        int area = 0;
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];

        Deque<Integer> stack = new ArrayDeque<Integer>();

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()]>heights[i]){
                //设置有边界
                right[stack.peek()] = i;
                //弹出元素
                stack.pop();
            }
            left[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }

        for (int i = 0; i < len; i++) {
            area = Math.max(area,heights[i]*(right[i]-left[i]-1));
        }

        return area;

    }
}
